package datastructure.day01;

/**
 * @author: Gan
 * @date 2021/4/28 0028 15:10
 * @description:
 * 实现如上课提示的双向链表的api
 * 根据内容删除
 * 根据内容查找
 * 根据内容替换 栈
 * 选作: 根据下标操作
 **/
public class DLinked {
    private LNode head;
    private LNode tail;
    private int length;

    public boolean remove(int index) {
        LNode mid, pStr;
        int count = 0;
        //判断非法操作，则删除失败
        if (length == 0 || index > length - 1)
        {
            return false;
        }
        //若删除的是头结点
        if (index == 0) {
            mid = head.next;
            head.next = null;
            mid.pre = null;
            mid = head;
            length--;
            return true;
        }
        //若删除的是尾结点
        if (index == length - 1) {
            mid = tail.pre;
            tail.pre = null;
            mid.next = null;
            mid = tail;
            length--;
            return true;
        }
        //中间结点
        mid = head;
        while (mid.next != null) {
            count++;
            mid = mid.next;
            //找到了要删除的下标
            if (count == index) {
                pStr = mid.next;
                mid.pre.next = mid.next;
                pStr.pre = mid.pre;
                length--;
            }
        }
        return true;
    }

    public boolean add(String str) {
        //为空
        if (length == 0) {
            head = new LNode(null, str, null);
            tail = head;
            length++;
            return true;
        }
        //尾部添加
        tail.next = new LNode(tail, str, null);
        tail = tail.next;
        length++;
        return true;
    }

    public boolean contains(String str) {
        //若空链表，查找失败
        if (length == 0) {
            return false;
        }
        if (str == null) {
            //若是头结点
            if (str == head.value) {
                return true;
            }
            LNode mid = head;
            while (mid.next != null) {
                mid = mid.next;
                if (mid.value == null) {
                    return true;
                }
            }
        } else {
            //当查找的元素不是空时
            if (str.equals(head.value)) {
                //头结点就是要查找的
                return true;
            }
            LNode mid = head;
            while (mid.next != null) {
                mid = mid.next;
                if (mid.value.equals(str)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean replace(int index, String newValue) {
        LNode mid = head;
        int count = 0;
        //排除非法操作
        if (length == 0 || index > length) {
            return false;
        }
        while (mid.next != null) {
            mid = mid.next;
            count++;
            if (index == count) {
                mid.value = newValue;
                return true;
            }
        }
        return false;
    }

    class LNode {
        String value;
        LNode next;
        LNode pre;

        public LNode(LNode pre, String value, LNode next) {
            this.value = value;
            this.next = next;
            this.pre = pre;
        }
    }
}
